﻿using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class Node<T>
{
    private T data;    //数据域，存储数据的对象

    private Node<T> next;    //引用域，指向下一个对象

    //构造器
    public Node(T val, Node<T> p)
    {
        data = val;
        next = p;
    }

    public Node(T val)
    {
        data = val;
        next = null;
    }

    public Node()
    {
        data = default(T);       //default默认引用类型为null,值类型为0, 复合类型根据里面的值分配。
        next = null;
    }

    public T Data
    {
        get { return data; }
        set { data = value;}
    }

    public Node<T> Next
    {
        get { return next; }
        set { next = value; }
    }
}

public class LinkList<T> : IListDs<T>
{
    private Node<T> head;           //单链表头的引用,  head指向第一个节点，head.next 才是第一个节点

    public Node<T> Head
    {
        get { return head; }
        set { head = value; }
    }

    //构造器 
    public LinkList()
    {
        head = new Node<T>();
    }

    public int GetLength()
    {
        Node<T> p = head;       //这里把头文件赋值

        int len = 0;
        while (p.Next != null)
        {
            p = p.Next;               //这里给p赋第len个节点的值
            len++;
        }
        return len;
    }

    public void Clear()
    {
        head.Next = null; ;
    }

    public bool IsEmpty()
    {
        if (head.Next == null)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    public void Append(T item)
    {
        Node<T> q = new Node<T>(item);
        Node<T> p;

        if (head.Next != null)
        {
            p = head.Next;
            while (p.Next != null)
            {
                p = p.Next; 
            }
            p.Next = q;
        }
        else
        {
            head.Next = q;              //head.next 指向第一个节点， 把q的值赋值给第一节点
            return;
        }
    }

    public void Insert(T item, int location)       //插入元素item 到第 location 位置，  小于1 或者大于表长都不对
    {
        Node<T> q = head;
        Node<T> p = new Node<T>(item);
        int j = 1;

        while ( q.Next != null && j < location )
        {
            q = q.Next;          //获取第j -1 个节点
            j++;
        }

        if ( q == null || j > location )
        {
            Debug.Log("List is empty or position is error!");
            return;
        }

        p.Next = q.Next;
        q.Next = p;
    }

    public T Delete(int location)    //location为需要删除的
    {

        Node<T> q = head;
        int j = 1;

        while (q.Next != null && j < location)
        {
            q = q.Next;                //获取j - 1个节点
            j++;
        }

        if (q.Next == null || j > location)
        {
            Debug.Log("List is empty or position is error!");
            return default(T);
        }

        Node<T> temp = q.Next;
        q.Next = temp.Next;
        return temp.Data;
    }

    public T GetElem(int location)
    {
        Node<T> p = head.Next;
        int j = 1;

        while ( j < location)
        {
            p = p.Next;
            j++;
        }

        if ( p == null || j > location)         // 用 j> location 来排除 location < 1,  p != null 排除location > length
        {
            Debug.Log("List is empty or postion is error!");
            return  default(T);
        }

        return p.Data;
    }

    public int Locate(T value)
    {
        if (IsEmpty())
        {
            Debug.Log("List is empty!");
            return -1;
        }

        Node<T> p = head.Next;
        int j = 1;

        while (!p.Data.Equals(value))
        {
            if (p.Next != null)
            {
                p = p.Next;
                j++;
            }
            else
            {
                return -1;
            }
        }
        return j;
    }
}
